//
//  Tree.hpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/7/24.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#ifndef Tree_hpp
#define Tree_hpp

#include <stdio.h>
#include <iostream>

#define MaxSize 100

// 特殊的二叉树
// 满二叉树、完全二叉树、二叉排序树、平衡二叉树
// n0 = 1 + n2

typedef int ElemType;
// 二叉树又名二叉链表
typedef struct BiTNode {
    ElemType value;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 队列
typedef struct LNode {
    BiTNode *data;
    struct LNode *next;
} LNode;
typedef struct {
    LNode *rare, *front;
} Queue;

// *先序遍历*（递归）
void PreOrder(BiTree T);
// *中序遍历*（递归）
void MidOrder(BiTree T);
// *后序遍历*（递归）
void LastOrder(BiTree T);
// **树的深度**（递归）
int TreeDeep(BiTree T);
// *层次遍历*
void LevelOrder(BiTree T);

// 确定唯一二叉树（一定要有*中序*）
// 中序+前序
// 中序+后序
// 中序+层序

// 线索二叉树（基于*遍历序列*定义的前驱和后继）
// n个结点的二叉树有n+1个空链域，可以用来记录前驱和后继
// 中序线索，前序线索，后序线索
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag; // 左右线索标志
} ThreadNode, *ThreadTree;

// *** 中序线索化 ***
void CreateInThread(ThreadTree &T);

// *** 先序线索化 ***
void CreatePreThread(ThreadTree &T);

// *** 后序线索化 ***
void CreatePostThread(ThreadTree &T);

// *** 中序后继结点 ***
ThreadNode* InThreadNext(ThreadNode *p);

// *** 中序前驱节点 ***
ThreadNode* InThreadPrev(ThreadNode *p);

// *** 中序遍历 ***
void InThreadOrder(ThreadTree T);

// *** 逆向中序遍历 ***
void RevInThreadOrder(ThreadTree T);

// *** 先序后继结点 ***
ThreadNode* PreThreadNext(ThreadNode *p);

// ** 先序前驱结点 ***
ThreadNode* PreThreadPrev(ThreadNode *p);

// *** 后序前驱结点 ***
ThreadNode* LastThreadPrev(ThreadNode *p);

// *** 后序后继结点 ***
ThreadNode* LastThreadNext(ThreadNode *p);

// *** 双亲表示法（顺序存储） ***
// 增加结点算法：直接在数组尾部增加数据
// 删除结点算法：
// 1. 直接删除结点，将parent设为-1表示空位置
// 2. 删除结点后，把最后一个元素填补到空位中(推荐)
// 3. 删除结点的孩子结点
// 优点：方便查找双亲结点
// 缺点：查找孩子结点需要遍历
typedef struct {
    ElemType data;
    int parent;
} PTNode;

typedef struct {
    PTNode nodes[MaxSize];
    int n; // 结点数
} PTree;

// *** 孩子表示法（顺序+链式） ***
typedef struct CTNode {
    int child; // 孩子指针
    struct CTNode *next;
} CTNode;

typedef struct {
    ElemType data;
    CTNode *firstchild;
} CTBox;

typedef struct {
    CTBox nodex[MaxSize];
    int n, r; // 长度 / 跟结点
} Ctree;

// ***** ✨孩子兄弟表示法(链式存储) *****
// 树和二叉树的相互转化：左孩子右兄弟
// 森林和二叉树的相互转化：先把每个树转为二叉树，再把跟结点视作兄弟关系连接
typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
} CSNode, *CSTree;

// *** 树的先根遍历 ***
// 先访问根结点，再访问子树（深度优先）
// 树的先根遍历 = 二叉树的先序遍历 （孩子兄弟转化为二叉树）

// *** 树的后根遍历 ***
// 先访问子树，再访问根结点（深度优先）
// 树的后根遍历 = 二叉树的中序遍历 （孩子兄弟转化为二叉树）

// *** 树的层次遍历 ***
// 广度优先

// *** 森林的先序遍历 ***
// 依次对子树进行先根遍历
// 森林的先序遍历 = 二叉树的先序遍历

// *** 森林的中序遍历 ***
// 依次对子树进行后根遍历
// 森林的中序遍历 = 二叉树的中序遍历

// 树      森林     二叉树
// 先根遍历 先序遍历  先序遍历
// 后根遍历 中序遍历  中序遍历

// Binary Search Tree 二叉排序树
typedef struct BSTNode {
    int data;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

// ** 查找 **
BSTNode* BST_Search(BSTree T, int key);

// ** 插入 **
bool BST_Insert(BSTree &T, int key);

// ** 构造BST **
bool BST_Create(BSTree &T, int arr[], int n);

// BST删除操作
// 1. 被删除的结点只有左子树或右子树：直接用左子树或右子树替代即可
// 2. 被删除结点有左右子树：在右子树找到最小的结点代替（最左侧的结点，肯定没有左子树）
// 3. 被删除结点有左右子树：在左子树找到最大的结点代替（最右侧的结点，肯定没有右子树）

// 查找成功的Average Search Length：思考
// 查找失败的Average Search Length：思考

// 二叉排序树的查找效率O(h)
// 最好的查找效率：log2(n)

// ***** AVL 平衡二叉树(时间复杂度 / 最大高度：log2(n)) *****
// 关键：每个结点的平衡因子：｜左子树高度-右子树高度｜ <= 1
// 平衡二叉树的插入：插入结点后若不平衡，则找到最小不平衡子树进行调整

// LL插入：右旋
// RR插入：左旋
// LR插入：先左旋后右旋
// RL插入：先右旋后左旋

// ** AVL最小结点数 **
// Nh代表h层最少结点数：N0=0,N1=1,N2=2...
// Nh = Nh-1 + Nh-2 + 1

// **** 哈夫曼树 ****
// 结点的权：代表重要性
// 结点的带权路径长度WPL：权*路径长度
// 树的带权路径长度：叶子结点的带权路径长度之和
// 哈夫曼树：带权路径长度最小的二叉树
// 给定n个带权结点构造哈夫曼树
// 1. 选择2个权值最小的结点，作为新结点的左、右结点。新结点权值为左右结点之和
// 2. 重复1直到只剩下1棵树
// 哈夫曼树的性质：
// 1. 权值越小离跟结点越远
// 2. 结点总数为2n-1
// 3. 不存在度为1的结点
// 4. 哈夫曼树不唯一，但是WPL唯一
// 哈夫曼编码（可变长度编码）：哈夫曼树左路径为0，右路径为1

#endif /* Tree_hpp */
